/**
 * https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/submissions/
 * 1926. 迷宫中离入口最近的出口
 * medium 陈贝纯 2024.12.05
 * bfs
 */

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int n=maze.size();
        int m=maze[0].size();
        vector<int> dx={-1,1,0,0};
        vector<int> dy={0,0,1,-1};
        queue<pair<int,pair<int,int>>> q;
        q.push({entrance[0],{entrance[1],0}});
        maze[entrance[0]][entrance[1]]='+';
        while(!q.empty()){
            auto [x,second_pair]=q.front();
            auto [y,step]=second_pair;
            q.pop();
            for(int i=0;i<4;++i){
                int repx=x+dx[i];
                int repy=y+dy[i];
                if(repx>=0&&repx<n&&repy>=0&&repy<m&&maze[repx][repy]=='.'){
                    if(repx==0||repx==n-1||repy==0||repy==m-1)
                        return step+1;
                    maze[repx][repy]='+';
                    q.push({repx,{repy,step+1}});
                }
            }
        }
        return -1;
    }
};